package P4树形结构;

import P1线性结构.LinkedList;
import P1线性结构.List;

import java.util.Iterator;

public class HashMap<K extends Comparable<K>, V> implements Map<K, V> {
    private static final int[] capacity = {
            53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
            49157, 98317, 196613, 393241, 768433, 1572869, 3145739, 6291469,
            12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741
    };
    private int capacityIndex = 0;  //当前容量默认capacity[0] = 53
    private int size;   //整个哈希表元素的个数
    private int M;      //当前哈希表的容量 capacity[capacityIndex]
    private int upperTol = 1000; //单个桶的上限
    private int lowerTol = 500;  //单个桶的下限
    private AVLTreeMap<K, V>[] table;

    public HashMap() {
        M = capacity[capacityIndex];
        size = 0;
        table = new AVLTreeMap[M];
        for (int i = 0; i < table.length; i++) {
            table[i] = new AVLTreeMap<>();
        }
    }

    private int hash(K key) {
        return Math.abs(key.hashCode()) % M;
    }

    @Override
    public void put(K key, V value) {
        int index = hash(key);
        AVLTreeMap<K, V> map = table[index];
        if (map.contains(key)) {
            map.put(key, value);
        } else {
            map.put(key, value);
            size++;
            //是否扩容
            if (size > M * upperTol && capacityIndex + 1 < capacity.length) {
                capacityIndex++;
                resize(capacity[capacityIndex]);
            }
        }
    }

    @Override
    public V remove(K key) {
        int index = hash(key);
        AVLTreeMap<K, V> map = table[index];
        V ret = map.remove(key);
        if (ret != null) {
            size--;
            //是否缩容
            if (size < M * lowerTol && capacityIndex - 1 >= 0) {
                capacityIndex--;
                resize(capacity[capacityIndex]);
            }
        }
        return ret;
    }

    private void resize(int newLen) {
        AVLTreeMap<K, V>[] newTable = new AVLTreeMap[newLen];
        for (int i = 0; i < newTable.length; i++) {
            newTable[i] = new AVLTreeMap<>();
        }
        M = newLen;
        for (int i = 0; i < table.length; i++) {
            AVLTreeMap<K, V> map = table[i];
            TreeSet<K> set = (TreeSet<K>) map.keySet();
            Iterator<K> it = set.iterator();
            while (it.hasNext()) {
                K key = it.next();
                newTable[hash(key)].put(key, map.get(key));
            }
        }
        table = newTable;
    }

    @Override
    public boolean contains(K key) {
        return table[hash(key)].contains(key);
    }

    @Override
    public V get(K key) {
        return table[hash(key)].get(key);
    }

    @Override
    public V getOrDefault(K key, V defaultValue) {
        return table[hash(key)].getOrDefault(key, defaultValue);
    }

    @Override
    public void set(K key, V value) {
        table[hash(key)].set(key, value);
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public Set<K> keySet() {
        TreeSet<K> set = new TreeSet<>();
        for (int i = 0; i < table.length; i++) {
            AVLTreeMap<K, V> map = table[i];
            TreeSet<K> s = (TreeSet<K>) map.keySet();
            Iterator<K> it = s.iterator();
            while (it.hasNext()) {
                K key = it.next();
                set.add(key);
            }
        }
        return set;
    }

    @Override
    public List<V> values() {
        LinkedList<V> list = new LinkedList<>();
        for (int i = 0; i < table.length; i++) {
            AVLTreeMap<K, V> map = table[i];
            LinkedList<V> s = (LinkedList<V>) map.values();
            Iterator<V> it = s.iterator();
            while (it.hasNext()) {
                V value = it.next();
                list.add(value);
            }
        }
        return list;
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        TreeSet<Entry<K,V>> set = new TreeSet<>();
        for (int i = 0; i < table.length; i++) {
            AVLTreeMap<K, V> map = table[i];
            TreeSet<Entry<K,V>> s = (TreeSet<Entry<K,V>>) map.entrySet();
            Iterator<Entry<K,V>> it = s.iterator();
            while (it.hasNext()) {
                Entry<K,V> entry = it.next();
                set.add(entry);
            }
        }
        return set;
    }
}